/*
 * topological-hex, a program to compute combinatorial hexahedral meshes.
 *
 * Copyright (C) <2018> <Université catholique de Louvain (UCL), Belgique>
 *
 * List of the contributors to the development, description and complete
 * License: see LICENSE file.
 *
 * This program (topological-hex) is free software:
 * you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see COPYING file).  If not,
 * see <http://www.gnu.org/licenses/>.
 */

#ifndef SYMMETRY_H_
#define SYMMETRY_H_

#include "types.h"
#include "vertex_set.h"
#include "solver.h"
#include <stdbool.h>
#include <stdalign.h>

static inline
bool extend_permutation(vertex_index *permutation,
                        vertex_index *inv_permutation,
                        vertex_index in_nogood,
                        vertex_index in_state) {
  /* Unassigned vertices cannot be mapped to any vertex. */
  if (in_state == VERTEX_SET_MAX)
    return false;

  /* If both mapping entries are empty, add the pair to the bijection. */
  if (permutation[in_nogood] == VERTEX_SET_MAX) {
    if (inv_permutation[in_state] == VERTEX_SET_MAX) {
      permutation[in_nogood] = in_state;
      inv_permutation[in_state] = in_nogood;

      return true;
    }
    else
      return false;
  }
  else if (inv_permutation[in_state] == VERTEX_SET_MAX)
    return false;

  /* Ensure that both vertices match the known mapping. */
  if (permutation[in_nogood] != in_state ||
      inv_permutation[in_state] != in_nogood)
    return false;

  return true;
}

/**
 * Special indicaters used to encode the tree of no-goods in a linear structure.
 */
typedef enum no_goods_instruction {
  /** Followed by a vertex assignment */
  NO_GOODS_VERTEX_0,
  NO_GOODS_VERTEX_1,
  NO_GOODS_VERTEX_2,
  NO_GOODS_VERTEX_3,

  /** Followed by the children of the current node */
  NO_GOODS_DOWN,

  /** Followed by the four vertices that make up the face of the next
   *  hexahedron */
  NO_GOODS_FACE,

  /** Followed by the eight vertices of the next hexahedron.
   *
   * Use of this encoding is reserved for the shellable-only version of the
   * search algorithm.
   */
  NO_GOODS_HEX,
} no_goods_instruction;

/**
 * Stores the changes performed by @ref solver_start_branch so they can be
 * cancelled by @ref solver_undo_no_goods.
 */
typedef struct no_goods_delta {
  size_t size;
  hex_index old_hex_index;
  uint8_t old_bound_mask;
} no_goods_delta;

static inline
size_t solver_incremental_symmetry_entry_size(
  uint32_t num_vertices, uint32_t num_hexes) {
  /* permutation and its inverse */
  size_t offset = 2 * sizeof(vertex_index) * num_vertices;

  /* alignment */
  offset = (offset + alignof(uint64_t) - 1) & ~((size_t)(alignof(uint64_t) - 1));

  /* offset within the linearized tree */
  offset += sizeof(uint64_t);

  /* bit mask of visited hexahedra */
  offset += sizeof(uint64_t) * ((num_hexes + 63) / 64);

  return offset;
}

static inline
size_t solver_incremental_symmetry_data_size(
  uint32_t num_vertices, uint32_t num_hexes, uint32_t num_symmetries) {
  return
    sizeof(uint64_t) + /* bit mask for active symmetries */
    num_symmetries * solver_incremental_symmetry_entry_size(
      num_vertices, num_hexes);
}

static inline
size_t solver_incremental_symmetry_trail_size(solver *solver) {
  if (solver->symmetry_data)
    return solver_incremental_symmetry_data_size(
      solver->num_vertices, solver->num_hexes,
      popcount64(*(uint64_t*)solver->symmetry_data));
  else
    return 1;
}

/**
 * Configures the set of permutations that preserve the face lattice of the
 * input.
 *
 * This can save time by skipping subtrees symmetrical to already explored
 * portions of the search space. The requirement for this operation to be valid
 * is that permutation.
 *
 * @param symmetries The permutations to use as symmetries. Each permutation is
 *   encoded as an array `a` where `a[i] = j` means that the permutation
 *   replaces i by j.
 */
error_code solver_set_symmetries(solver *solver,
                                 size_t num_symmetries,
                                 uint32_t num_boundary_vertices,
                                 const vertex_index *symmetries);

/**
 * Automatically finds the set of symmetries of a mesh.
 *
 * This is equivalent to @ref solver_set_symmetries called with all the
 * symmetries of the boundary.
 */
error_code solver_compute_symmetries(solver *solver);

/**
 * @return The number of bytes needed to perform incremental symmetry breaking.
 */
size_t solver_incremental_symmetry_data_size(
  uint32_t num_vertices, uint32_t num_hexes, uint32_t num_symmetries);

/**
 * Called before each branching node to maintain the state of no-goods.
 *
 * This is used to break symmetries: if a node is a subtree of a no-good (up to
 * symmetry), it can be pruned.
 *
 * When backtracking, this operation can be cancelled along with subsequent
 * calls to @ref solver_is_no_good.
 *
 * @param [out] delta Changes performed by this function, so that they can
 *   be cancelled.
 */
error_code solver_start_branch(solver *solver, no_goods_delta *delta);

/**
 * Indicates that binding @p i to @p v from the current node produces a subtree
 * that has already been explored.
 *
 * Changes are added to the existing delta structure so that a single function
 * call can undo both new and existing change.
 *
 * @see solver_start_branch
 */
error_code solver_is_no_good(solver *solver,
                             quad_vertex_index i, vertex_index v,
                             no_goods_delta *delta);

error_code solver_hex_is_no_good(solver *solver, no_goods_delta *delta);

/**
 * Cancels calls to @ref solver_start_branch and @ref solver_is_no_good.
 */
void solver_undo_no_goods(solver *solver, const no_goods_delta *delta);

/**
 * Domination-testing, used to break symmetries
 *
 * @return true if the current solver state is dominated by a no-good.
 */
bool is_dominated(solver *solver);

void incremental_symmetry_data_trail(const solver *solver, uint8_t *trail);

void incremental_symmetry_data_restore(solver *solver, const uint8_t *trail);

bool incremental_domination_test(solver *solver);

bool find_symmetry(vertex_index *quads, uint32_t num_quads,
                   uint32_t num_vertices,
                   quad_index q_a, quad_index q_b,
                   uint8_t offset, bool flip,
                   bool *seen_a, bool *seen_b,
                   vertex_index *permutation,
                   vertex_index *inv_permutation);

#endif
